package main

import "fmt"

/*
二分查找

前提：数组有序
定义左右和中间位置索引
判断中间索引位置值值与目标值大小关系，
如果小于目标值，左索引等于中间索引
如果大于目标值，右索引等于中间索引
如果等于目标值，直接返回中间索引
重新计算中间索引
循环
直到右索引减左索引小于等于2
*/
func search(nums []int, target int) int {
	leftIndex := 0
	rightIndex := len(nums) - 1

	for leftIndex <= rightIndex {
		middleIndex := (leftIndex + rightIndex) / 2
		middleValue := nums[middleIndex]

		if middleValue == target {
			return middleIndex
		}

		if middleValue < target {
			leftIndex = middleIndex + 1
		} else {
			rightIndex = middleIndex - 1
		}
	}

	return -1
}

func L704() {
	fmt.Println(search([]int{-1, 0, 3, 5, 9, 12}, 2))
}
